#include <bits/stdc++.h>
using namespace std;

/*


96. 不同的二叉搜索树
已解答
中等
相关标签
相关企业
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

 

示例 1：


输入：n = 3
输出：5
示例 2：

输入：n = 1
输出：1
 

提示：

1 <= n <= 19
*/

class Solution {
	public:
	int numTrees(int n) {
		vector<long long> dp(n + 1, 0); // 二叉搜索树的数量
		dp[0] = 1;
		dp[1] = 1;
		for(int i = 2; i <= n; ++i) {
			for(int j = 1; j <= i; ++j) {
				dp[i] += dp[j - 1] * dp[i - j];
			}
		}
		return dp[n];
	}
};